package com.zjsru.oneDay202203;

/**
 * @Author: likew
 * @Date: 2022/3/15
 *
 * 统计  按位或  能得到最大值的子集数目
 *  输入：nums = [3,1]
 * 输出：2
 * 解释：子集按位或能得到的最大值是 3 。有 2 个子集按位或可以得到 3 ：
 * - [3]
 * - [3,1]
 *
 * 输入：nums = [3,2,1,5]
 * 输出：6
 * 解释：子集按位或可能的最大值是 7 。有 6 个子集按位或可以得到 7 ：
 * - [3,5]
 * - [3,1,5]
 * - [3,2,5]
 * - [3,2,1,5]
 * - [2,5]
 * - [2,1,5]
 *
 */
public class countMaxOrSubsets {
    /*二进制枚举*/
    public int countMaxOrSubsets(int[] nums) {
        int len = nums.length,mask = 1<<len;
        int max = 0,ans =0;
        for (int i = 0; i < mask; i++) {
            int cur = 0;
            for (int j = 0; j < len; j++) {
                if((((i>>j)&1)==1)){
                    cur |= nums[j];
                }
            }
            if(cur > max){
                max = cur;
                ans = 1;
            }else if(cur == max){
                ans ++;
            }
        }
        return ans;
    }
    
    public static void main(String[] args) {
        countMaxOrSubsets countMaxOrSubsets = new countMaxOrSubsets();
        int[] nums = new int[]{3,2,1,5};
        System.out.println(countMaxOrSubsets.countMaxOrSubsets(nums));
    }
}
